#ifndef TIM_GRAPH_H
#define TIM_GRAPH_H
#include "tim_list.h"
#include "tim_bintree.h"
#include "tim_stack&tim_queue.h"
#include "tim_vector.h"
#include "tim_hashtable.h"

namespace tim
{
	template<typename T>
	class vertex
	{
		public:
			T data;//数据域
			int in_degree, out_degree;//出度，入度
			bool status;//状态
			vertex(T d = T(), int i = 0, int o = 0, int s = false):
				data(d), in_degree(i), out_degree(o), status(s) {};
	};

	template<typename Tv, typename Te>
	class edge
	{
		public:
			Te data;//数据域
			int weight;//权重
			bool status;//状态
			tim::vertex<Tv>* point_to;//指向的图结点
			edge(Te d = (Te)0, int w = 0, tim::vertex<Tv>* p = nullptr, bool s = false):
				data(d), weight(w), point_to(p), status(s) {};
	};

	template<typename Tv, typename Te>
	class graph
	{
		private:
			tim::list<vertex<Tv>> V;//顶点集
			tim::list<tim::list<edge<Tv, Te>>> E;//边集
			int _edges;

		public:
			Tv& operator[] (int n) { return V[n].data;};//取结点
			int in_degree (int n) { return V[n].in_degree;};
			int out_degree (int n)  { return V[n].out_degree;};
			int degree(int n) { return V[n].in_degree + V[n].out_degree;};
			int edges() {return _edges;};//返回边数
			int vertexs() {return V.size();};
			graph() {};
			graph(Tv* elements, int** weights, int n);//接受长l的顶点元素集, 和対应的领接矩阵， 时空间复杂度均为o（n）, 先行后列
			graph(Tv* elements, Te** connections, int** weights, int n);//接受长l的顶点元素集，和对应的领接矩阵、包含边元素，时空间复杂度均为o（n）, 先行后列
			void insert_vertex(Tv const& e);//插入结点， 接受描述其边关系的数组，时间复杂度o（n），因为尾插
			void insert_edge(int a, int b, int w, Te e);//插入边，时间复杂度
			void insert_edge(int a, int b, int w);//插入边，无元素
			void remove_vertex(int n);//删除结点
			void remove_edge(int a, int b);//删除边
			int find(Tv const& e);//查找当元素的秩
			template<typename VST>
			void BFS(int n, VST& visit);//广度优先搜索
			template<typename VST>
			void DFS(int n, VST& visit);//深度优先搜索
			tim::vector<int>& Dijkstra(int a, int b);//最短路径
			tim::vector<int>& Floyd(int n);//最短路径
			tim::graph<Tv, Te>& prim(int n);//最小生成树, o(n3)复杂度
			tim::graph<Tv, Te>& kruskal(int n);//最小生成树
			tim::vector<int>& tsort();//拓扑排序
			template<typename VST>
			void sparseprint(VST& visit)
			{
				for (int i = 0; i < E.size(); i++)
					for (int j = 0; j < E[i].size(); j++)
						std::cout<<"\n", visit(E[i][j].weight);
			};//列表打印, 测试用
	};
}

template<typename Tv, typename Te>
tim::graph<Tv, Te>::graph(Tv* elements, int** weights, int n): _edges(0)
{
	for (int i = 0; i < n; i++) {
		int in = 0, out = 0;
		E.insert_back(tim::list<edge<Tv, Te>>());
		for (int j = 0; j < n; j++) {
			if (weights[i][j] > 0) in++;
			if (weights[i][j] < 0) out++;
			if (weights[i][j] != 0) _edges++;
		}
		V.insert_back(vertex<Tv>(elements[i], in, out));
	}

	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			if (weights[i][j] != 0)
				E[i].insert_back(edge<Tv, Te>(Te(), weights[i][j], &V[j]));
}

template<typename Tv, typename Te>
tim::graph<Tv, Te>::graph(Tv* elements, Te** connections, int** weights, int n): _edges(0)
{
	for (int i = 0; i < n; i++) {
		int in = 0, out = 0;
		E.insert_back(tim::list<edge<Tv, Te>>());
		for (int j = 0; j < n; j++) {
			if (weights[i][j] > 0) in++;
			if (weights[i][j] < 0) out++;
			if (weights[i][j] != 0) _edges++;
		}
		V.insert_back(vertex<Tv>(elements[i], in, out));
	}

	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			if (weights[i][j] != 0)
				E[i].insert_back(edge<Tv, Te>(connections[i][j], weights[i][j], &V[j]));
}

template<typename Tv, typename Te>
void tim::graph<Tv, Te>::insert_vertex(const Tv &e)
{
	V.insert_back(tim::vertex<Tv>(e));
	E.insert_back(tim::list<tim::edge<Tv, Te>>());
}

template<typename Tv, typename Te>
void tim::graph<Tv, Te>::insert_edge(int a, int b, int w)
{
	E[a].insert_back(tim::edge<Tv, Te>((Te)0, w, &V[b]));
	V[a].out_degree++;
	V[b].in_degree++;
	_edges++;
}

template<typename Tv, typename Te>
void tim::graph<Tv, Te>::insert_edge(int a, int b, int w, Te e)
{
	E[a].insert_back(tim::edge<Tv, Te>(e, w, &V[b]));
	V[a].out_degree++;
	V[b].in_degree++;
	_edges++;
}

template<typename Tv, typename Te>
void tim::graph<Tv, Te>::remove_vertex(int n)
{
	for (int i = 0; i < E[n].size(); i++)
		E[n][i].point_to->in_degree--;//减掉入度

		for (int i = 0; i < E.size(); i++)
			for (int j = 0; i < E[i].size(); j++)
				if (E[i][j].point_to == &V[n]) {
					E[i].remove(j);
					V[i].out_degree--;//减掉出度
				}

		V.remove(n); E.remove(n);
}

template<typename Tv, typename Te>
void tim::graph<Tv, Te>::remove_edge(int a, int b)
{
	for (int i = 0; i < E[a].size(); i++)
		if (E[a][i].point_to == &V[b]) E[a].remove(i);
	V[a].out_degree--;
	V[b].in_degree--;
	_edges--;
}

template<typename Tv, typename Te>
int tim::graph<Tv, Te>::find(Tv const& e)
{
	for (int i = 0; i < V.size(); i++)
		if (V[i].data == e) return i;

	return -1;
}

template<typename Tv, typename Te>
template<typename VST>
void tim::graph<Tv, Te>::BFS(int n, VST &visit)
{
	tim::queue<vertex<Tv>*> wait;
	wait.enqueue(&V[n]);

	while (!wait.empty()) {
		if (wait.front()->status == false) visit(wait.front()->data);
		wait.front()->status = true;
		int rank = find(wait.front()->data);

		for (int i = 0; i < E[rank].size(); i++)
			if (E[rank][i].point_to->status == false)
				wait.enqueue(E[rank][i].point_to);

		wait.dequeue();
	}

	for (int i = 0; i < V.size(); i++) V[i].status = false;
}

template<typename Tv, typename Te>
template<typename VST>
void tim::graph<Tv, Te>::DFS(int n, VST &visit)
{
	tim::stack<vertex<Tv>*> wait;
	wait.push(&V[n]);
	int temp = 0;

	while (!wait.empty()) {
		temp = find(wait.top()->data);
		for (int i = 0; i < E[temp].size(); i++)
			if (E[temp][i].point_to->status == false and wait.find(E[temp][i].point_to) == -1) {
				wait.push(E[temp][i].point_to);
				break;
			}

		if (temp == find(wait.top()->data)) {
			if (wait.top()->status == false) visit(wait.top()->data);
			wait.top()->status = true;
			wait.pop();
		}
	}

	for (int i = 0; i < V.size(); i++) V[i].status = false;
}

template<typename Tv, typename Te>
tim::vector<int>& tim::graph<Tv, Te>::Dijkstra(int a, int b)
{
	struct node_info
	{
		int length;
		bool mark;
		int before;
	};

	tim::vector<node_info> wait(V.size());
	tim::vector<int>* most_short = new tim::vector<int>;
	int cnt = 0;

	for (int i = 0; i < wait.size(); i++) wait[i].length = INT32_MAX, wait[i].mark = false, wait[i].before = -1;
	wait[a].length = 0;
	most_short->append(a);

	while (!wait[b].mark and cnt++ < wait.size()) {
		int temp = a;
		for (int i = 0; i < wait.size(); i++)
			if (temp == a and !wait[i].mark) temp = i;
			else if (!wait[i].mark and wait[i].length < wait[temp].length) temp = i;

		wait[temp].mark = true;
		for (int i = 0; i < E[temp].size(); i++)
			if (wait[temp].length + E[temp][i].data < wait[i].length) {
				wait[i].length = wait[temp].length + E[temp][i].data;
				wait[i].before = temp;
			}

		most_short->append(temp);
	}

	return *most_short;
}

template<typename Tv, typename Te>
tim::graph<Tv, Te>& tim::graph<Tv, Te>::prim(int n)
{
	int _size = V.size();

	Tv* elements = new Tv[_size];
	for (int i = 0; i < _size; i++)
		elements[i] = V[i].data;

	int** c = new int*[_size];
	for (int i = 0; i < _size; i++) c[i] = new int[_size];
	for (int i = 0; i < _size; i++)
		for (int j = 0; j < _size; j++)
			c[i][j] = 0;

	Te** connections = new Te*[_size];
	for (int i = 0; i < _size; i++) connections[i] = new Te[_size];

	V[n].status = true;
	for (int i = 0; i < _size - 1; i++) {
		int min_rank;
		int last_rank;
		int neighbor_order;
		int min_weight = INT32_MAX;

		for (int j = 0; j < V.size(); j++)
			for (int k = 0; k < E[j].size(); k++)
				if (V[j].status = true and E[j][k].point_to->status != true)
					if (E[j][k].weight < min_weight) {
						last_rank = find(V[j].data);
						min_rank = find(E[j][k].point_to->data);
						neighbor_order = k;

						min_weight = E[j][k].weight;
					}

		V[min_rank].status = true;
		c[last_rank][min_rank] = E[last_rank][neighbor_order].weight;
		connections[last_rank][min_rank] = E[last_rank][neighbor_order].data;
	}
	tim::graph<Tv, Te>* new_graph = new graph<Tv, Te>(elements, connections, c, _size);

	delete[] elements;
	for (int i = 0; i < _size; i++) delete[] connections[i];

	delete[] connections;
	for (int i = 0; i < _size; i++) delete[] c[i];

	delete[] c;
	for (int i = 0; i < _size; i++) V[i].status = false;

	return *new_graph;
}


/*template<typename Tv, typename Te>
tim::graph<Tv, Te>& tim::graph<Tv, Te>::kruskal(int n)
{
	int _size = V.size();

	Tv* elements = new Tv[_size];
	for (int i = 0; i < _size; i++)
		elements[i] = V[i].data;

	int** c = new int*[_size];
	for (int i = 0; i < _size; i++) c[i] = new int[_size];
	for (int i = 0; i < _size; i++)
		for (int j = 0; j < _size; j++)
			c[i][j] = 0;

	Te** connections = new Te*[_size];
	for (int i = 0; i < _size; i++) connections[i] = new Te[_size];




	tim::graph<Tv, Te>* new_graph = new graph<Tv, Te>(elements, connections, c, _size);

	delete[] elements;
	for (int i = 0; i < _size; i++) delete[] connections[i];

	delete[] connections;
	for (int i = 0; i < _size; i++) delete[] c[i];

	delete[] c;
	for (int i = 0; i < _size; i++) V[i].status = false;

	return *new_graph;
}

template<typename Tv, typename Te>
tim::vector<int>& tim::graph<Tv, Te>::Floyd(int n)
{

}*/

#endif
